from typing import *


class Solution:

    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        h = [[False] * n for _ in range(n)]
        for i in range(n):
            for j in range(i, -1, -1):
                if s[j] == s[i] and (i - j <= 1 or h[j + 1][i - 1]):
                    h[j][i] = True

        def f(id=0):
            if id == n:
                ans.append(arr.copy())
                return
            for i in range(id + 1, n + 1):
                if h[id][i - 1]:
                    arr.append(s[id:i])
                    f(i)
                    arr.pop()

        ans, arr = [], []
        f()
        return ans


so = Solution()
print(so.partition(s="google"))
